#pragma once

#include <cstddef>
#include <cstring>
#include <utility>

#include "ezstl_iterator_base.hpp"
#include "type_traits.hpp"

namespace ezstl {

template <typename InputIterator1, typename InputIterator2>
bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2) {
  for (; first1 != last1; ++first1, (void)++first2)
    if (*first1 != *first2) return false;
  return true;
}

template <typename InputIterator1, typename InputIterator2,
          typename BinaryPredicate>
bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2,
           BinaryPredicate binary_op) {
  for (; first1 != last1; ++first1, (void)++first2)
    if (!binary_op(*first1, *first2)) return false;
  return true;
}

template <typename ForwardIterator, typename T>
void fill(ForwardIterator first, ForwardIterator last, const T &value) {
  for (; first != last; ++first) *first = value;
}

template <typename OutputIterator, typename Size, typename T>
OutputIterator fill_n(OutputIterator first, Size n, const T &value) {
  for (; n > 0; ++first, (void)--n) *first = value;
  return first;
}

template <typename ForwardIterator1, typename ForwardIterator2>
void iter_swap(ForwardIterator1 a, ForwardIterator2 b) {
  using value_type = typename iterator_traits<ForwardIterator1>::value_type;
  value_type tmp = *a;
  *a = *b;
  *b = tmp;
}

template <typename T>
inline const T &max(const T &a, const T &b) {
  return a < b ? b : a;
}
template <typename T, typename Compare>
inline const T &max(const T &a, const T &b, Compare comp) {
  return comp(a, b) ? a : b;
}

template <typename T>
inline const T &min(const T &a, const T &b) {
  return a < b ? a : b;
}
template <typename T, typename Compare>
inline const T &min(const T &a, const T &b, Compare comp) {
  return comp(b, a) ? a : b;
}

/**
 * @brief
 * 以类似字符串比较的方式比较两个序列，第一序列以字典排列方式小于第二序列返回true
 *
 * @tparam InputIterator1
 * @tparam InputIterator2
 * @param first1
 * @param last1
 * @param first2
 * @param last2
 * @return true
 * @return false
 */
template <typename InputIterator1, typename InputIterator2>
bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
                             InputIterator2 first2, InputIterator2 last2) {
  for (; first1 != last1 && first2 != last2; ++first1, ++first2) {
    if (*first1 < *first2) return true;
    if (*first2 < *first1) return false;
  }
  return first1 == last1 && first2 != last2;
}

inline bool lexicographical_compare(const unsigned char *first1,
                                    const unsigned char *last1,
                                    const unsigned char *first2,
                                    const unsigned char *last2) {
  const size_t len1 = last1 - first1;
  const size_t len2 = last2 - first2;
  const auto result =
      memcmp(first1, first2, ezstl::min(last1 - first1, last2 - first2));
  return result ? (result < 0) : (len1 < len2);
}

template <typename InputIterator1, typename InputIterator2>
std::pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1,
                                                   InputIterator1 last1,
                                                   InputIterator2 first2) {
  while (first1 != last1 && *first1 == *first2) {
    ++first1;
    ++first2;
  }
  return std::make_pair(first1, first2);
}

template <typename InputIterator1, typename InputIterator2,
          typename BinaryPredicate>
std::pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1,
                                                   InputIterator1 last1,
                                                   InputIterator2 first2,
                                                   BinaryPredicate pred) {
  while (first1 != last1 && pred(*first1, *first2)) {
    ++first1;
    ++first2;
  }
  return std::make_pair(first1, first2);
}

template <typename T>
inline void swap(T &a, T &b) {
  T tmp = a;
  a = b;
  b = tmp;
}

template <typename RandomAccessIterator, typename OutputIterator,
          typename Distance>
OutputIterator __copy_d(RandomAccessIterator first, RandomAccessIterator last,
                        OutputIterator result, Distance) {
  for (Distance n = last - first; n > 0; --n, (void)++result, (void)++first)
    *result = *first;  // assignment operator
  return result;
}

template <typename InputIterator, typename OutputIterator>
OutputIterator __copy(InputIterator first, InputIterator last,
                      OutputIterator result, input_iterator_tag) {
  for (; first != last; ++first, (void)++result) *result = *first;
  return result;
}

template <typename RandomAccessIterator, typename OutputIterator>
OutputIterator __copy(RandomAccessIterator first, RandomAccessIterator last,
                      OutputIterator result, random_access_iterator_tag) {
  using distance_type =
      typename iterator_traits<RandomAccessIterator>::difference_type;
  return __copy_d(first, last, result, distance_type());
}

template <typename InputIterator, typename OutputIterator>
struct __copy_dispatch {
  OutputIterator operator()(InputIterator first, InputIterator last,
                            OutputIterator result) {
    using category = typename iterator_traits<InputIterator>::iterator_category;
    __copy(first, last, category());
  }
};

template <typename T>
T *__copy_t(const T *first, const T *last, T *result, true_type) {
  memmove(result, first, last - first);
  return result + (last - first);
}

template <typename T>
T *__copy_t(const T *first, const T *last, T *result, false_type) {
  return __copy_d(first, last, result, ptrdiff_t());
}

template <typename T>
struct __copy_dispatch<T *, T *> {
  T *operator()(T *first, T *last, T *result) {
    using has_trivial_assignment_operator = typename is_pod<T>::type;
    return __copy_t(first, last, result, has_trivial_assignment_operator());
  }
};

template <typename T>
struct __copy_dispatch<const T *, T *> {
  T *operator()(const T *first, const T *last, T *result) {
    using has_trivial_assignment_operator = typename is_pod<T>::type;
    return __copy_t(first, last, result, has_trivial_assignment_operator());
  }
};

template <typename InputIterator, typename OutputIterator>
inline OutputIterator copy(InputIterator first, InputIterator last,
                           OutputIterator result) {
  return __copy_dispatch<InputIterator, OutputIterator>()(first, last, result);
}

inline char *copy(const char *first, const char *last, char *result) {
  memmove(result, first, last - first);
  return result + (last - first);
}

inline wchar_t *copy(const wchar_t *first, const wchar_t *last,
                     wchar_t *result) {
  memmove(result, first, sizeof(wchar_t) * (last - first));
  return result + (last - first);
}

template <typename BidirectionalIterator1, typename BidirectionalIterator2>
BidirectionalIterator2 copy_backward(BidirectionalIterator1 first,
                                     BidirectionalIterator1 last,
                                     BidirectionalIterator2 result) {
  while (first != last) {
    *--result = *--last;
  }
  return result;
}

}  // namespace ezstl